/*
 * @lc app=leetcode.cn id=421 lang=cpp
 *
 * [421] 数组中两个数的最大异或值
 */

// @lc code=start
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
class Solution
{
public:
    set<int> s[2][2];

    bool split2(int from, int to, int nth)
    {
        if (s[from][0].size() && s[from][1].size())
        {
            int tmp = 1 << nth;

            for (auto n : s[from][0])
            {
                if (!(n & tmp))
                {
                    s[to][0].insert(n);
                }
            }

            for (auto n : s[from][1])
            {
                if (n & tmp)
                {
                    s[to][1].insert(n);
                }
            }

        }
        return s[to][0].size() && s[to][1].size();
    }

    // bool split(int from, int to, int nth)
    // {
    //     int tmp = 1 << nth;

    //     for (auto n : s[from][0])
    //     {
    //         if (n & tmp)
    //         {
    //             s[to][1].insert(n);
    //         }
    //         else
    //         {
    //             s[to][0].insert(n);
    //         }
    //     }

    //     for (auto n : s[from][1])
    //     {
    //         if (n & tmp)
    //         {
    //             s[to][1].insert(n);
    //         }
    //         else
    //         {
    //             s[to][0].insert(n);
    //         }
    //     }

    //     s[from][0].clear();
    //     s[from][1].clear();

    //     return s[to][0].size() && s[to][1].size();
    // }
    int findMaximumXOR(vector<int> &nums)
    {
        if (nums.size() < 2)
            return 0;

        int msb = 0;
        {
            int max_int = *max_element(nums.begin(), nums.end());
            while (max_int)
            {
                msb++;
                max_int >>= 1;
            }
        }

        {
            int tmp = 1 << (msb-1);
            for (auto n : nums)
            {
                if (n & tmp)
                    s[0][1].insert(n);
                else
                    s[0][0].insert(n);
            }
        }
        int ans = 0;
        int from = 0, to = 1;
        for (int i = msb - 1; i >= 0; i--)
        {
            if (split2(from, to, i))
            {
                ans |= 1 << i;
            }
            swap(to, from);
        }
        return ans;
    }
};

int main()
{
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    Solution().findMaximumXOR(nums);
    return 0;
}
// @lc code=end
